package TenBasicAlgorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

//贪心算法(局部最优)
public class GreedyAlgorithmDemo {
    public static void main(String[] args) {
        HashMap<String, HashSet> broadcasts=new HashMap<>();
        HashSet<String>hashSet1=new HashSet<>();
        hashSet1.add("bj");
        hashSet1.add("sh");
        hashSet1.add("tj");
        HashSet<String>hashSet2=new HashSet<>();
        hashSet2.add("gz");
        hashSet2.add("bj");
        hashSet2.add("sz");
        HashSet<String>hashSet3=new HashSet<>();
        hashSet3.add("cd");
        hashSet3.add("sh");
        hashSet3.add("hz");
        HashSet<String>hashSet4=new HashSet<>();
        hashSet4.add("sh");
        hashSet4.add("tj");
        HashSet<String>hashSet5=new HashSet<>();
        hashSet5.add("hz");
        hashSet5.add("dl");
        broadcasts.put("k1",hashSet1);
        broadcasts.put("k2",hashSet2);
        broadcasts.put("k3",hashSet3);
        broadcasts.put("k4",hashSet4);
        broadcasts.put("k5",hashSet5);
        HashSet<String>all=new HashSet<>();
        all.addAll(hashSet1);
        all.addAll(hashSet2);
        all.addAll(hashSet3);
        all.addAll(hashSet4);
        all.addAll(hashSet5);
        System.out.println(all);
        ArrayList<String> arrayList=new ArrayList<>();
        HashSet<String> tempSet=new HashSet<>();
        String maxKey=null;
        while (all.size()>0){
            for(String key:broadcasts.keySet()){
                tempSet.clear();
                HashSet<String> areas=broadcasts.get(key);
                tempSet.addAll(areas);
                tempSet.retainAll(all);
                if(tempSet.size()>0&&(maxKey==null||tempSet.size()>broadcasts.get(maxKey).size())){//更新最大未覆盖key值
                    maxKey=key;
                }
            }if(maxKey!=null){
                arrayList.add(maxKey);
                all.removeAll(broadcasts.get(maxKey));
            }
            maxKey=null;

        }

        System.out.println(arrayList);
    }

}
